package com.zx._12_算法.左程云算法练习;

import com.zx._12_算法.Nums;

/**
 *
 */
public class Case_05 {

    public static void main(String[] args) {
        int[] res = Nums.res;
        Nums.printRes();
        System.out.println(findK(res, 7));

        Nums.printRes();
        System.out.println(findMostLeftNoLessKIndex(res, 5));
        System.out.println(findMostLeftNoLessKIndex(res, -1));
        System.out.println(findMostLeftNoLessKIndex(res, 10));

        Nums.printRes();
        System.out.println(findMostRightNoMoreKIndex(res, 5));
        System.out.println(findMostRightNoMoreKIndex(res, -1));
        System.out.println(findMostRightNoMoreKIndex(res, 10));
    }

    /**
     * 有序数组中找到num:   二分查找
     *
     * @param nums
     * @param target
     * @return 找到target的索引值，未找到返回-1
     */
    private static int findK(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        //保存结果
        int resIdx = -1;
        int len = nums.length;

        int begin = 0;
        int end = len;

        while (begin <= end) {
            int mid = (end + begin) / 2;

            if (nums[mid] == target) {
                resIdx = mid;
                break;
            }
            //判断左右
            if (nums[mid] < target) {
                // 目标值在右边
                begin = ++mid;
                end = end;
            } else {
                begin = begin;
                end = --mid;
            }
        }

        return resIdx;
    }

    /**
     * 在有序数组中，找到 nums[i] >= k 的数字的最左边的值
     *
     * @param nums
     * @param k
     * @return
     */
    private static int findMostLeftNoLessKIndex(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= k) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;

    }

    /**
     * 在有序数组中，找到 nums[i] <= k 的数字的最右边的值
     *
     * nums = 0,1,2,3,4,5,6, k = 2 , idx = 2;
     *
     * @param nums
     * @param k
     * @return
     */
    private static int findMostRightNoMoreKIndex(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= k) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;

    }

}
